package cc.wsyw126.java.nowcoder.leetCode;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by dp on 2017/4/20.
 * Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
 */
public class MaxPointsOnALine {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) return 0;
        int result = 0;
        for (int i = 0; i < points.length; i++) {
            HashMap<Double, Integer> k = new HashMap<>();
            int v = 0, dup = 1;
            for (int j = i + 1; j < points.length; j++) {
                if (points[i].x == points[j].x) {
                    if (points[i].y == points[j].y) {
                        dup++;
                    } else {
                        v++;
                    }
                } else {
                    double v1 = 0.0;
                    if (points[i].y - points[j].y != 0) {
                        v1 = (points[i].y - points[j].y) * 1.0 / (points[i].x - points[j].x);
                    }
                    Integer integer = k.get(v1);
                    if (integer == null) {
                        integer = 0;
                    }
                    integer++;
                    k.put(v1, integer);
                }
            }
            for (Map.Entry<Double, Integer> doubleIntegerEntry : k.entrySet()) {
                if (v < doubleIntegerEntry.getValue()) {
                    v = doubleIntegerEntry.getValue();
                }
            }
            result = result >= v + dup ? result : v + dup;
        }
        return result;
    }

    private class Point {
        int x;
        int y;

        Point() {
            x = 0;
            y = 0;
        }

        Point(int a, int b) {
            x = a;
            y = b;
        }
    }

    public static void main(String[] args) {
        MaxPointsOnALine maxPointsOnALine = new MaxPointsOnALine();
        Point point = maxPointsOnALine.new Point();
        Point point1 = maxPointsOnALine.new Point(1, 1);
        Point point2 = maxPointsOnALine.new Point(2, 2);
        Point point3 = maxPointsOnALine.new Point(2, 0);
//        int i = maxPointsOnALine.maxPoints(new Point[]{point, point1, point2,point3});

        Point point0 = maxPointsOnALine.new Point(2, 3);
        Point point01 = maxPointsOnALine.new Point(3, 3);
        Point point02 = maxPointsOnALine.new Point(-5, 3);

        int i = maxPointsOnALine.maxPoints(new Point[]{point0, point01, point02});
        System.out.println("i = " + i);
    }
}
